package formal.array;

/**
 * @author DengYuan2
 * @create 2021-02-06 21:45
 */
public class M_287 {
    public static void main(String[] args) {
//        int[] nums={1,3,4,2,2};
        int[] nums={1,1};
        int res = findDuplicate(nums);
        System.out.println(res);

    }


    /**
     * 我的思路-将数值放到正确的位置上
     * 但是，进阶要求的是不修改数组，时间复杂度<O(n2)，额外空间为O(1)
     * @param nums
     * @return
     */
    public static int findDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; ) {
            int x= nums[i];
            if (x!=i+1){
                int y =nums[x-1];
                if (x!=y){
                    nums[i]=y;
                    nums[x-1]=x;
                }else {
                    return x;
                }
            }else {
                i++;
            }
        }
        return 0;
    }

    /**
     * 大神-二分法！！
     * @param nums
     * @return
     */
    public static int findDuplicate2(int[] nums){
        int left=1;
        //因为有一个重复的数，所以最大的数是nums.length-1
        int right =nums.length-1;
        while (left<=right){
            int mid = (left+right)/2;
            int count=0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i]<=mid){
                    count++;
                }
            }
            if (count>mid){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return left;
    }
}
